package com.shangguigu.recursive.exc;

/**
 * @author: ZhouBert
 * @date: 2019/10/12
 * @description:	迷宫问题
 * 0-表示可以走的路；1-表示墙；2-表示走过的路；3-表示走过走不通的路死路
 */
public class TheMaze {
	/**
	 * 定义一个 6 行 7 列的迷宫
	 * todo:作为全局变量，供递归方法修改迷宫路径【即被递归方法共享！写递归的时候需要考虑什么变量需要被递归方法共享】
	 */
	int[][] maze;
	/**
	 * 出口i索引位置
	 */
	int exitI;
	/**
	 * 出口j索引位置
	 */
	int exitJ;

	public TheMaze(int[][] maze, int i,int j) {
		this.maze = maze;
		exitI=i;
		exitJ=j;
	}

	/**
	 * 迷宫探索。
	 * --策略：下-右-左-上
	 * todo:当一个节点为3时，将会回溯到上一个调用它的方法中，并将其置为3。--所以需要有回溯的想法，要经常想是谁导致这个结果【回溯】
	 * @param i
	 * @param j
	 * @return
	 */
	public boolean setWay(int i,int j){
		///如果走过终点，说明已经达到终点
		if (maze[exitI][exitJ]==2){
			showMaze();
			return true;
		}else{
			///1.如果还没走过
			if (maze[i][j]==0){
				maze[i][j]=2;
				///1.下
				if (setWay(i+1,j)){
					showMaze();
					return true;
				}
				///2.右
				else if(setWay(i,j+1)){
					showMaze();
					return true;
				}
				///3.左
				else if(setWay(i,j-1)){
					showMaze();
					return true;
				}
				///4.上
				else if(setWay(i-1,j)){
					showMaze();
					return true;
				}else {
					maze[i][j]=3;
					showMaze();
					return false;
				}
			}
			///2.如果该点是-墙1；走过2；死路3
			else{
				showMaze();
				return false;
			}

		}
	}

	/**
	 * 打印迷宫
	 */
	public void showMaze(){
		System.out.println("--");
		for (int[] row:
			 maze) {
			for (int item:
				 row) {
				System.out.printf("%d\t",item);
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		///1.构造迷宫
		int[][] myMaze=new int[8][7];
		///1.1将第一行和最后一行置1
		for (int i = 0; i < 7; i++) {
			myMaze[0][i]=1;
			myMaze[7][i]=1;
		}
		///1.2将第一列和最后一列置1
		for (int i = 0; i < 8; i++) {
			myMaze[i][0]=1;
			myMaze[i][6]=1;
		}
		///1.3设置阻碍墙
		myMaze[3][1]=1;
		myMaze[3][2]=1;
		myMaze[6][4]=1;

		TheMaze theMaze = new TheMaze(myMaze, 6,5);

		theMaze.showMaze();
		System.out.println("--开始探寻迷宫--");
		theMaze.setWay(1,1);
		theMaze.showMaze();

	}



}
